package offer;

import java.util.HashMap;

/**
 * @author ZhanBo
 * @date 2020/6/7
 */
public class Solution7 {
    /**
     * 中序
     */
    HashMap<Integer, Integer> dic = new HashMap<>();
    /**
     * 前序
     */
    int[] po;

    /**
     * 面试题07. 重建二叉树
     *
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     *
     * 前序遍历 preorder = [3,9,20,15,7]
     * 中序遍历 inorder = [9,3,15,20,7]
     * 返回如下的二叉树：
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        po = preorder;
        for(int i = 0; i < inorder.length; i++) {
            dic.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length - 1);
    }
    /**
     * @param preRoot 前序遍历中根节点的索引
     * @param inLeft 中序遍历左边界
     * @param inRight 中序遍历右边界
     * @return
     */
    private TreeNode recur(int preRoot, int inLeft, int inRight) {
        if(inLeft > inRight) {
            return null;
        }
        TreeNode root = new TreeNode(po[preRoot]);
        //root索引
        int i = dic.get(po[preRoot]);
        //左节点
        root.left = recur(preRoot + 1, inLeft, i - 1);
        //右节点
        root.right = recur(preRoot + i - inLeft + 1, i + 1, inRight);
        return root;
    }

    public static void main(String[] args) {
        Solution7 solution7 = new Solution7();
        int [] preorder = {3,9,20,15,7};
        int [] inorder = {9,3,15,20,7};
        solution7.buildTree(preorder,inorder);
    }
}
